package com.bupt.leetcode;

import java.util.Stack;

/**
 * 未分类的leetcode题目
 * @author Frank
 *
 */
public class OthersAlgorithm {
	class Point{
		int x;
		int y;
		public Point(int x,int y) {
			this.x = x ;
			this.y = y;
		}
		public boolean equals(Point obj) {
			return x == obj.x && y== obj.y;
		}
	}
	/**
	 * 
	 * @param grid
	 * @return
	 */
    public int numIslands(char[][] grid) {
        if(grid == null ) return 0;
    	boolean[][] visited  = new boolean[grid.length][grid[0].length];
        int k = 0;
        for(int i = 0;i<grid.length;i++){
        	for(int j = 0; j< grid[i].length;j++){
        		if(grid[i][j] == '1' && visited[i][j] == false){
        			k++;
        			DFS(grid,visited,i,j);
        		}
        	}
        }
        return k;
    }
    /**
     * 深度优先搜索算法
     * @param grid
     * @param visited
     * @param i
     * @param j
     */
    private void DFS(char[][]grid,boolean[][] visited,int i,int j){
    	Stack<Point> s = new Stack<Point>();
    	s.push(new Point(i,j));
    	visited[i][j] = true;
    	while(!s.empty()){
    		Point p = s.peek();
    		if(p.y > 0 &&  grid[p.x][p.y-1] == '1' &&  !visited[p.x][p.y-1]){
    			s.push(new Point(p.x,p.y-1));
    			visited[p.x][p.y-1] = true;
    			continue;
    		}
    		if(p.x > 0 && grid[p.x-1][p.y] == '1' && !visited[p.x-1][p.y]){
    			s.push(new Point(p.x-1,p.y));
    			visited[p.x-1][p.y] = true;
    			continue;
    		}
    		if( p.x < grid.length-1 && grid[p.x+1][p.y] == '1' && !visited[p.x+1][p.y]){
    			s.push(new Point(p.x+1,p.y));
    			visited[p.x+1][p.y] = true;
    			continue;
    		}
    		if(p.y < grid[0].length -1 && grid[p.x][p.y+1] == '1' && !visited[p.x][p.y+1]){
    			s.push(new Point(p.x,p.y+1));
    			visited[p.x][p.y+1] = true;
    			continue;
    		}
    		s.pop();
    	}
	}
}
